package top.humbleyuan.linkedlist;

import top.humbleyuan.datastructure.linkedlist.LinkNode;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 22:26
 * @Des 对链表进行插入排序
 */
public class LeetCode_147 {

    /**
     * 对链表进行插入排序
     * 1.一个指针往后遍历
     * 2.每次遍历与前一个比对：
     *      2.1若大于等于前一个，继续往前
     *      2.2否则另取指针从头遍历，在刚好的位置插入，
     *
     *###注意要调整断开以及连接点的连接关系
     *###在设root节点的时候注意考虑首次root和head是不需要交换的
     */

     public static void main(String[] args) {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(-2147483647);
        int[] vals = {-2147483648};
        head = LinkNode.formLink(head,vals);
        LinkNode root = new LinkNode(-1);
        root.next = head;

        LinkNode moveTemp = head;
        LinkNode preTemp = root;

        while (moveTemp != null) {

            if(moveTemp.val >= preTemp.val || moveTemp == head) {
                preTemp = moveTemp;
                moveTemp = moveTemp.next;
                continue;
            }

            LinkNode sortTemp = root.next;
            LinkNode preSortTemp = root;
            while (sortTemp != moveTemp) {
                if(sortTemp.val > moveTemp.val) {
                    LinkNode temp = moveTemp;
                    moveTemp = moveTemp.next;
                    preTemp.next = moveTemp;

                    preSortTemp.next = temp;
                    temp.next = sortTemp;
                    break;
                }
                preSortTemp = sortTemp;
                sortTemp = sortTemp.next;
            }

        }

        LinkNode.headToString(root.next);
    }
}
